# 作者: 陈其志 
# 2025年02月23日10时55分52秒 
# 2716847110@qq.com
# 什么是完全二叉树：每个节点没有空的子节点
class Node:
    """
    实例化一个二叉树对象的时候没有左右节点，所以复制None
    """

    def __init__(self, value=-1, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


class Tree:
    """
    二叉树的类
    """

    def __init__(self):
        self.root = None
        # 层次建树必须用辅助队列
        self.queue = []

    def build_tree(self, value):
        """
        每次只进来一个节点
        :param value:
        :return:
        """
        # 进来一个数，实例化一个节点
        new_node = Node(value)
        # 入辅助队列：
        self.queue.append(new_node)
        if self.root is None:
            self.root = new_node
        else:
            if self.queue[0].left is None:
                self.queue[0].left = new_node
            else:
                self.queue[0].right = new_node
                # 出队po)头部出队
                #                 self.queue.pop(0)p(0

    def pre_ord(self, node: Node):
        """
        前序遍历
        :param node:
        :return:
        """
        if node:
            print(node.value, end=' ')
            self.pre_ord(node.left)
            self.pre_ord(node.right)

    def mid_ord(self, node: Node):
        """
        中序遍历
        :param node:
        :return:
        """
        if node:
            self.mid_ord(node.left)
            print(node.value, end=' ')
            self.mid_ord(node.right)

    def end_ord(self, node: Node):
        """
        后续遍历
        :param node:
        :return:
        """
        if node:
            self.end_ord(node.left)
            self.end_ord(node.right)
            print(node.value, end=' ')

    def level_ord(self):
        # 层序遍历需要辅助队列
        self.queue.clear()
        self.queue.append(self.root)
        while self.queue:
            node = self.queue.pop(0)  # 出队获得当前节点
            print(node.value, end=' ')
            if node.left:
                self.queue.append(node.left)
            if node.right:
                self.queue.append(node.right)


if __name__ == '__main__':
    tree = Tree()
    # 建树
    for i in range(1, 11):
        tree.build_tree(i)

    # 前序遍历(递归)  深度优先遍历
    tree.pre_ord(tree.root)
    print()
    # 中序遍历
    tree.mid_ord(tree.root)
    print()
    # 后序遍历
    tree.end_ord(tree.root)
    print()
    # 层序遍历 广度优先遍历
    tree.level_ord()
